/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-01-06
 * Time:14:55
 */

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 贪心算法:1005. K 次取反后最大化的数组和
 * 简单
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 *     选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 * 示例 1：
 * 输入：nums = [4,2,3], k = 1
 * 输出：5
 * 解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 */

/**
 * 假设整个数组中有 m 哥负数
 * 1.m > k,把前 k 个小的数变为正数
 * 2.m == k，把全部负数变为正数
 * 3.m < k,
 *        3.1:把所有负数变为整数
 *        3.2: k - m的奇偶性：
 *            3.2.1:偶数:直接忽略，break
 *            3.2.2:奇数，挑选当前数组中最小的数变为负数
 */
public class largestSumAfterKNegations {
    public static void main(String[] args) {
        largestSumAfterKNegations(new int[]{2,-3,-1,5,-4},3);
    }
    public static int largestSumAfterKNegations(int[] nums, int k) {
        int m = 0,len = nums.length;
        int ret = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < len; i++) if (nums[i] < 0) m++;
        if (m == k){
            for (int i = 0; i < len; i++) {
                if (nums[i] < 0) nums[i] = -nums[i];
            }
        }else if (m > k){
            for (int i = 0; i < len; i++) {
                queue.add(nums[i]);
            }
        }else {
            for (int i = 0; i < len; i++) {
                if (nums[i] < 0) nums[i] = -nums[i];
            }
            if ((k - m) % 2 != 0){
                int j = 1;
                int index = 0;
                for (int i = 0; i < len; i++) {
                    if(j == len) break;
                    if (nums[index] < nums[j]){
                        j++;
                    }else {
                        index = j;
                        j++;
                    }
                }
                nums[index] = -nums[index];
            }
        }
        for (int i = 0; i < len; i++) {
            ret += nums[i];
        }
        if (m > k){
            for (int i = 0; i < k; i++) {
                ret += -(queue.poll() * 2);
            }
        }
        return ret;
    }
}
